package need_learn.coding.didi;
/**
 * TODO 滴滴， 数组去重，然后输出最后的最短数组 长度，题目描述：给你一个有序数组 numbs ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。O(1) 额外空间
 *     //   不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
 *
 * @author david
 * @version 1.0
 * @date 2021/4/20 14:56
 */
public class removeDuplicates {

    public static void main(String[] args) {
        int[] numbs=new int[] {0,0,1,1,1,2,2,3,3,4};
        System.out.println(delDuplicates(numbs));
        for (int a:numbs){
            System.out.println(a);
        }
    }

    /**
     * 双指针解法：  相等就移动快指针j,不相等就移动慢指针i，并赋值给nums[++left]=nums[right];
     * 时间复杂度为O(n)，空间复杂度为O(1)
     * @param numbs
     * @return
     */
    public static int delDuplicates(int[] numbs){
        //边界值判断
        if(numbs==null|| numbs.length==0){
            return 0;
        }
        int left=0;
        //循环
        for(int right=1;right<numbs.length;right++){
            //如果发现左右两个不一致就把左指针加一，然后赋值right当前坐标值给left
            if(numbs[left]!=numbs[right]){
                left++;
                numbs[left]=numbs[right];
            }
        }
        return left;
    }
}
